package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * @author Administrator
 * @date 2020/6/24 10:03
 */
public class StringOperation {
    /**
     * 反转字符串 II
     * 给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
     * 如果剩余字符少于 k 个，则将剩余字符全部反转。
     * 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
     */
    @Test
    public void reverseStr() {
        Assert.assertEquals("bacdfeg", reverseStr("abcdefg", 2));
    }

    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();
        if (s.length() < k) {
            reverse(chars, 0, chars.length);
        } else if (s.length() < 2 * k) {
            reverse(chars, 0, k);
        } else {
            for (int i = 0; i < chars.length; i += 2 * k) {
                reverse(chars, i, chars.length - i >= k ? i + k : chars.length);
            }
        }
        return new String(chars);
    }

    /**
     * 反转字符串中的单词 III
     * 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
     */
    @Test
    public void reverseWords() {
        Assert.assertEquals("s'teL ekat edoCteeL tsetnoc", reverseWords("Let's take LeetCode contest"));
    }

    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int start = 0;
        for (int i = 0; i < chars.length; i++) {
            if (' ' == chars[i]) {
                reverse(chars, start, i);
                start = i + 1;
            }
        }
        reverse(chars, start, chars.length);
        return new String(chars);
    }

    /**
     * 反转字符串中的元音字母
     * 编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
     */
    @Test
    public void reverseVowels() {
        Assert.assertEquals("holle", reverseVowels("hello"));
        Assert.assertEquals("leotcede", reverseVowels("leetcode"));
    }

    public String reverseVowels(String s) {
        // 先将字符串转成字符数组（方便操作）
        // 以上是只针对 Java 语言来说的 因为 chatAt(i) 每次都要检查是否越界 有性能消耗
        char[] arr = s.toCharArray();
        int n = arr.length;
        int l = 0;
        int r = n - 1;
        while (l < r) {
            // 从左判断如果当前元素不是元音
            while (l < n && !isVowel(arr[l])) {
                l++;
            }
            // 从右判断如果当前元素不是元音
            while (r >= 0 && !isVowel(arr[r])) {
                r--;
            }
            // 如果没有元音
            if (l >= r) {
                break;
            }
            // 交换前后的元音
            swap(arr, l, r);
            // 这里要分开写，不要写进数组里面去
            l++;
            r--;
        }
        // 最后返回的时候要转换成字符串输出
        return new String(arr);
    }

    private void swap(char[] arr, int a, int b) {
        char tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    // 判断是不是元音，如果不是元音才返回 true
    private boolean isVowel(char ch) {
        // 这里要直接用 return 语句返回，不要返回 true 或者 false
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
                || ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U';
    }


    public void reverse(char[] bytes, int start, int end) {
        char[] tmp = new char[end - start];
        System.arraycopy(bytes, start, tmp, 0, end - start);
        for (int i = start; i < end; i++) {
            bytes[i] = tmp[end - i - 1];
        }
    }

    /**
     * 实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。
     */
    @Test
    public void toLowerCase() {
        Assert.assertEquals("hello", toLowerCase("Hello"));
        Assert.assertEquals("hello", toLowerCase("hello"));
        Assert.assertEquals("hello", toLowerCase("HELLo"));
    }

    public String toLowerCase(String str) {
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] < 65 || chars[i] > 90) {
            } else {
                chars[i] = (char) (chars[i] + 32);
            }
        }
        return new String(chars);
    }

    /**
     * 串联所有单词的子串
     * 给定一个字符串 s 和一些长度相同的单词 words。
     * 找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
     * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
     */
    @Test
    public void findSubstring() {
        Assert.assertArrayEquals(new Integer[]{0, 9}, findSubstring("barfoothefoobarman", new String[]{"foo", "bar"}).toArray(new Integer[0]));
        Assert.assertArrayEquals(new Integer[]{}, findSubstring("wordgoodgoodgoodbestword", new String[]{"word", "good", "best", "word"}).toArray(new Integer[0]));
        Assert.assertArrayEquals(new Integer[]{8}, findSubstring("wordgoodgoodgoodbestword", new String[]{"word", "good", "best", "good"}).toArray(new Integer[0]));
    }

    public List<Integer> findSubstring(String s, String[] words) {
        if (words.length == 0) {
            return new ArrayList<>();
        }
        int len = words[0].length();
        Map<String, Integer> allWords = new HashMap<>();
        for (String word : words) {
            allWords.compute(word, (e, o) -> {
                if (o == null) return 1;
                else return o + 1;
            });
        }
        List<Integer> res = new ArrayList<>();
        //遍历所有子串
        for (int i = 0; i < s.length() - words.length * len + 1; i++) {
            //HashMap2 存当前扫描的字符串含有的单词
            Map<String, Integer> hasWords = new HashMap<>();
            int num = 0;
            //判断该子串是否符合
            while (num < words.length) {
                String word = s.substring(i + num * len, i + (num + 1) * len);
                //判断该单词在 HashMap1 中
                if (allWords.containsKey(word)) {
                    int value = hasWords.getOrDefault(word, 0);
                    hasWords.put(word, value + 1);
                    //判断当前单词的 value 和 HashMap1 中该单词的 value
                    if (hasWords.get(word) > allWords.get(word)) {
                        break;
                    }
                } else {
                    break;
                }
                num++;
            }
            //判断是不是所有的单词都符合条件
            if (num == words.length) {
                res.add(i);
            }
        }
        return res;
    }

    /**
     * 恢复空格
     * 哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。
     * 像句子"I reset the computer. It still didn’t boot!"
     * 已经变成了"iresetthecomputeritstilldidntboot"。
     * 在处理标点符号和大小写之前，你得先把它断成词语。
     * 当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。
     * 假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。
     */
    @Test
    public void respace() {
        Assert.assertEquals(7, respace(new String[]{"looked", "just", "like", "her", "brother"}, "jesslookedjustliketimherbrother"));
        Assert.assertEquals(63, respace(new String[]{"wccm", "wiw", "uwwiwcmiiiwmmwicuwu", "mw"}, "iwiwwwmuiccwwwwwmumwwwmcciwwuiwcicwwuwicuiwciwmiwicwuwwmuimccwucuuim"));
    }

    public int respace(String[] dictionary, String sentence) {
        int n = sentence.length();

        Trie root = new Trie();
        for (String word : dictionary) {
            root.insert(word);
        }

        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] + 1;

            Trie curPos = root;
            for (int j = i; j >= 1; --j) {
                int t = sentence.charAt(j - 1) - 'a';
                if (curPos.next[t] == null) {
                    break;
                } else if (curPos.next[t].isEnd) {
                    dp[i] = Math.min(dp[i], dp[j - 1]);
                }
                if (dp[i] == 0) {
                    break;
                }
                curPos = curPos.next[t];
            }
        }
        return dp[n];
    }

    class Trie {
        public Trie[] next;
        public boolean isEnd;

        public Trie() {
            next = new Trie[26];
            isEnd = false;
        }

        public void insert(String s) {
            Trie curPos = this;

            for (int i = s.length() - 1; i >= 0; --i) {
                int t = s.charAt(i) - 'a';
                if (curPos.next[t] == null) {
                    curPos.next[t] = new Trie();
                }
                curPos = curPos.next[t];
            }
            curPos.isEnd = true;
        }
    }

    /**
     * 亲密字符串
     * 给定两个由小写字母构成的字符串 A 和 B ，
     * 只要我们可以通过交换 A 中的两个字母得到与 B 相等的结果，就返回 true ；否则返回 false 。
     */
    @Test
    public void buddyStrings() {
        Assert.assertTrue(buddyStrings("ab", "ba"));
        Assert.assertTrue(buddyStrings("aa", "aa"));
        Assert.assertFalse(buddyStrings("ab", "ab"));
        Assert.assertFalse(buddyStrings("", "ab"));
        Assert.assertTrue(buddyStrings("aaaaaaabc", "aaaaaaacb"));
    }

    public boolean buddyStrings(String A, String B) {
        if (A.length() != B.length()) {
            return false;
        }
        if (A.equals(B)) {
            int[] count = new int[26];
            for (int i = 0; i < A.length(); ++i) {
                if (++count[A.charAt(i) - 'a'] > 1) {
                    return true;
                }
            }
            return false;
        }
        int first = -1, second = -1;
        for (int i = 0; i < A.length(); ++i) {
            if (A.charAt(i) != B.charAt(i)) {
                if (first == -1) {
                    first = i;
                } else if (second == -1) {
                    second = i;
                } else {
                    return false;
                }
            }
        }

        return (second != -1 && A.charAt(first) == B.charAt(second) &&
                A.charAt(second) == B.charAt(first));
    }

    /**
     * 字符串相加
     * 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
     */
    @Test
    public void addStrings() {
        Assert.assertEquals("0", addStrings("0", "0"));
    }

    public String addStrings(String num1, String num2) {
        if (num1.length() < num2.length()) {
            return addStrings(num2, num1);
        }
        int index1 = num1.length() - 1, index2 = num2.length() - 1, add = 0;
        char[] res = new char[num1.length() + 1];
        while (index1 >= 0 && index2 >= 0) {
            int sum = (num1.charAt(index1) - '0') + (num2.charAt(index2) - '0') + add;
            if (sum > 9) {
                add = 1;
                sum %= 10;
            } else {
                add = 0;
            }
            res[index1 + 1] = (char) (sum + '0');
            index1--;
            index2--;
        }
        while (index1 >= 0) {
            int sum = (num1.charAt(index1) - '0') + add;
            if (sum > 9) {
                add = 1;
                sum %= 10;
            } else {
                add = 0;
            }
            res[index1 + 1] = (char) (sum + '0');
            index1--;
        }
        if (add > 0) {
            res[0] = '1';
            return new String(res);
        }
        return new String(res, 1, num1.length());
    }

    /**
     * 字符串相乘
     * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，
     * 它们的乘积也表示为字符串形式。
     */
    @Test
    public void multiply() {
        Assert.assertEquals("6", multiply("1", "6"));
        Assert.assertEquals("0", multiply("1", "0"));
        Assert.assertEquals("0", multiply("999", "0"));
        Assert.assertEquals("56088", multiply("123", "456"));
        Assert.assertEquals("998001", multiply("999", "999"));
    }

    public String multiply(String num1, String num2) {
        if (num1.length() < num2.length()) {
            return multiply(num2, num1);
        }
        char[] m = new char[num1.length() + num2.length()];
        Arrays.fill(m, '0');
        int add = 0;
        for (int i = num2.length() - 1; i >= 0; i--) {
            int c1 = num2.charAt(i) - '0';
            for (int j = num1.length() - 1; j >= 0; j--) {
                int c2 = num1.charAt(j) - '0';
                int multi = c1 * c2 + add + (m[i + j + 1] - '0');
                add = multi / 10;
                m[i + j + 1] = (char) (multi % 10 + '0');
            }
            if (add > 0) {
                m[i] = (char) (add + '0');
                add = 0;
            }
        }
        int i = 0;
        for (; i < m.length; i++) {
            if (m[i] > '0') {
                break;
            }
        }
        if (i == m.length) {
            i = m.length - 1;
        }
        return new String(m, i, m.length - i);
    }
}
